<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      class Node {
        constructor(key) {
          this.key = key;
          this.left = null; // 左指针
          this.right = null; // 右指针
        }
      }
      // 用来标记计算结果
      const compare = {
        LESS_THAN: -1, // 小于
        BIGGER_THAN: 1, // 大于
        EQUALS: 0, // 等于
      };

      // 封装二叉树
      class BST {
        constructor() {
          // 根节点
          this.root = null;
        }

        // -----------------------------------------------------------------------------------------
        // 添加方法
        insert(value) {
          // 判断情况 根节点是否为空
          if (this.root == null) {
            this.root = new Node(value);
          } else {
            // 此时  需要使用递归  因为不知道二叉树的深度  所以需要一直去判断
            this.insertNode(this.root, value);
          }
        }

        // 单独封装一个方法 用来判断如果添加的value比原来的node小  那么添加到左节点 否则去右节点
        insertNode(node, value) {
          // 如果是小于的情况
          if (this.compareFn(value, node.key) === compare.LESS_THAN) {
            if (node.left == null) {
              // 到最后一层停止
              node.left = new Node(value);
            } else {
              // 一直递归调用
              this.insertNode(node.left, value);
            }
          } else {
            if (node.right == null) {
              node.right = new Node(value);
            } else {
              this.insertNode(value, node.right);
            }
          }
        }

        // 计算方法单独封装
        compareFn(a, b) {
          if (a === b) {
            return compare.EQUALS;
          }
          return a < b ? compare.LESS_THAN : compare.BIGGER_THAN;
        }

      }

      const tree = new BST();

  

    </script>
  </body>
</html>
